MOD = 998244353
N = 3 * 10 ** 5 + 1
fac = [1] * N
rev = [1] * N
f = [1] * N
for i in range(2, N):
f[i] = (f[i - 1] + (i - 1) * f[i - 2]) % MOD
for i in range(2, N):
fac[i] = fac[i - 1] * i % MOD
rev[i] = pow(fac[i], MOD - 2, MOD)
def C(n, k):
return fac[n] * rev[k] % MOD * rev[n - k] % MOD
def solve(n):
res = 0
for i in range(n):
if 4 * i > n:
break
res = (res + C(n - 2 * i, 2 * i) * fac[2 * i] * rev[i] * f[n - 4 * i]) % MOD
print(res % 998244353)
t = int(input())
for _ in range(t):
n = int(input())
solve(n) // ॐ
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
#define pb push_back
#define Sort(a) sort(a.begin(),a.end())
#define ff first
#define ss second
const int N = 3e5 + 10;
const ll f = 998244353;
vll fact(N,1),ifact(N,1),pairs(N,1);
ll binpow(ll a, ll b) {
ll res = 1;
while (b > 0) {
if (b & 1)
res = res * a % f;
a = a * a % f;
b >>= 1;
}
return res;
}
ll nCr(int n, int r){
ll t = (ifact[r]*ifact[n-r])%f;
return (t * fact[n])%f;
}
void pre(){
for (int i = 2; i < N; ++i){
fact[i]=(fact[i-1]*i)%f;
}
for (int i = 1; i < N; ++i){
ifact[i]=binpow(fact[i],f-2);
}
for (int i = 2; i < N; ++i){
pairs[i] = (pairs[i-1] + pairs[i-2]*(i-1))%f;
}
}
void solve(){
int n;
cin>>n;
ll ans = 0;
for (int i = 0; i <= n; i+=4){
ll t = nCr(n-i/2,i/2);
ll g = (fact[i/2]*ifact[i/4])%f;
t = (t * g)%f;
t = (t * pairs[n-i])%f;
ans+=t; ans%=f;
}
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
pre();
int t=1;
cin>>t;
while(t--)
solve();
}
1009E - Intercity Travelling | 1637B - MEX and Array |
224A - Parallelepiped | 964A - Splits |
1615A - Closing The Gap | 4C - Registration System |
1321A - Contest for Robots | 1451A - Subtract or Divide |
1B - Spreadsheet | 1177A - Digits Sequence (Easy Edition) |
1579A - Casimir's String Solitaire | 287B - Pipeline |
510A - Fox And Snake | 1520B - Ordinary Numbers |
1624A - Plus One on the Subset | 350A - TL |
1487A - Arena | 1520D - Same Differences |
376A - Lever | 1305A - Kuroni and the Gifts |
1609A - Divide and Multiply | 149B - Martian Clock |
205A - Little Elephant and Rozdil | 1609B - William the Vigilant |
978B - File Name | 1426B - Symmetric Matrix |
732B - Cormen --- The Best Friend Of a Man | 1369A - FashionabLee |
1474B - Different Divisors | 1632B - Roof Construction |